package 栈队列与哈希表;

import java.util.ArrayDeque;
import java.util.HashSet;

public class G如何实现LRU缓存方案 {

    /**
     * 可以使用两个数据结构实现一个LRU缓存。
     * 1）使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用的过程中，
     * 把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾的位置。
     * 2）使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。
     * 当引用一个页面时，所需的页面在内存中，
     * 需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中，将它存储在内存中。
     * 简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更新相应的结点地址。
     * 如果队列是满的，那么就从队列尾部移除一个结点，并将新结点添加到队列的前面
     */
    private int cacheSize;
    private ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
    private HashSet<Integer> hashSet = new HashSet<>();

    public G如何实现LRU缓存方案(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    //判断缓存队列是否已满
    private boolean isQueueFull() {
        return queue.size() == cacheSize;
    }

    //把页号为pageNum的也缓存到队列中，同时也添加到Hash表中
    private void enqueue(int pageNum) {
        //如果队列满了，需要删除队尾的缓存的页
        if (isQueueFull()) {
            hashSet.remove(queue.getLast());
            queue.pollLast();
        }
        queue.addFirst(pageNum);
        //把新缓存的节点同时添加到hash表中
        hashSet.add(pageNum);
    }

    /**
     * 当访问某一个page的时候会调用这个函数，对于访问的page有两种情况
     * 1，如果page在缓存队列中，直接把这个节点移动到队首
     * 2，如果page不在缓存队列中，把这个page缓存到队首
     */
    public void accessPage(int pageNum) {
        //page不在缓存队列汇总，把它缓存到队首
        if (!hashSet.contains(pageNum)) {
            enqueue(pageNum);
        } else if (pageNum != queue.getFirst()) {
            queue.remove(pageNum);
            queue.addFirst(pageNum);
        }
    }

    public void printQueue() {
        while (!queue.isEmpty()) {
            System.out.print(queue.pop() + " ");
        }
    }

    public static void main(String[] args) {
        //假设缓存大小为3
        G如何实现LRU缓存方案 lru = new G如何实现LRU缓存方案(3);

        //访问page
        lru.accessPage(1);
        lru.accessPage(2);
        lru.accessPage(5);

        lru.accessPage(1);
        lru.accessPage(6);
        lru.accessPage(7);
        //通过上面的访问序列后，缓存的信息为
        lru.printQueue();
    }
}
